Engineering drawings are often scanned into computer systems and stored in electronic form in order to more easily manage such drawings. Many of these drawings have a tabular or quasi-tabular structure in which horizontal and vertical lines form rectangular tabular cells. Examples of such structured drawings include telephone company drawings, such as assignment drawings, wiring lists, front equipment drawings and distributing frame drawings. Due to the large size of the drawings, scanned images are often encoded, specifically using run length encoding or enhancements such as the TIFF group 4 format, to reduce the amount of memory required to store the images.
Once the structured drawings are scanned into the computer system, their scanned images are analyzed and processed to convert them into computer aided design ("CAD") and data representation, a form that is easy to manipulate and query on computers. Typically, the lines of a scanned image are initially detected by the computer system. Then, the cells of the drawings are identified based on the positions of these lines, and the text contained in each cell is identified using optical character recognition ("OCR") techniques. Thus, the result is a vector and computer data representation of the information contained in the original drawings.
The operation of scanning these structured drawings causes distortions in the scanned images, such as global skew, speckles, very dark and/or faint scanning. Traditionally, structured drawings, particularly telephone company drawings, have been drafted on large sheets of Mylar. Due to the large size of the Mylar drawings, the drawings can become misaligned as they are fed through the scanner which can cause the horizontal and vertical lines of the drawings to appear skewed. Although simple realignment processes are known, such processes are not able to compensate for the skew effect, due to the fact that the drawings often have uneven and warped surfaces that further distort the lines. Over the years, Mylar sheets have been subjected to wear and tear by being processed through copying, drafting, filming, and scanning equipment. The ink of the drawings tends to detach from the Mylar sheets over time due to the wear and tear and, thus, results in fragmented lines in the drawings. In most cases, this wear and tear has caused extensive local warping, shearing effects and other distortions to develop in the Mylar sheets, which are carried over to the scanned image.
The process of eliminating the skew from structured drawings is difficult and time consuming. Due to the difficulties in compensating for the skew effect, a highly accurate line detection technique is required. In addition, large structured drawings, particularly engineering drawings, cause the process of correcting the skew to be intolerably lengthy. Such engineering drawings may be, for example, about 3 feet by 4 feet in size and, at 300 dots per inch and one byte per pixel, about 155 MBytes in size.
The cells of a structured drawing do not necessarily conform to standard layouts. In fact, the vast majority of engineering drawings have unique layouts in which the number of columns and rows vary, cells are subdivided and/or cells are merged with other adjacent cells. Thus, unlike simple forms processing, identification of cells cannot be accomplished by simply extracting data to a standard layout. Each structured drawing must be processed and interpreted without presumptions about its structure or layout.
Traditional straight line detection algorithms, such as vectorization by thinning, polygonal approximation and the Hough transform, do not work well on the distorted scanned images of structured drawings. For example, U.S. Pat. No. 3,069,654 to P.V.C. Hough, which issued on Dec. 18, 1962, entitled METHOD AND MEANS FOR RECOGNIZING COMPLEX PATTERNS, provides a Hough transform method for analyzing straight line segments of an image and transforming each line segment into a transform plane. In particular, each point along an individual line segment is transcribed as a separate line in the transform plane. By carefullly positioning the lines of the transform plane and determining the intersection point of the lines, slope and intercept data for each line segment may be stored and later analyzed for the presence of desired patterns. However, the Hough transform method cannot tolerate significant warping and skew contained within scanned images of drawings. In addition, this method is computationally expensive and slow when applied to large images, such as those for engineering drawings.
In contrast to the traditional straight line detection algorithms described above, faster and more convenient methods for detecting substantially horizontal and vertical lines are known. However, such methods still require substantial processing time and make numerous mistakes when analyzing skewed or noisy images. In particular, a sparse pixel based method for line finding called Orthogonal Zig Zag ("OZZ") is described in articles entitled "Orthogonal Zig-Zag: An Efficient Method for Extracting Bars in Engineering Drawings" by I. Chai and D. Dori, Visual Form: Analysis and Recognition, edited by C. Arcelli, L. Cordella and G. Sanniti di Baja (Plenum Press, New York, 1992) pp. 127-136 and "Sparse-pixel Recognition of Primitives in Engineering Drawings" by D. Dori, Y. Liang, J. Dowell, and I. Chai, Machine Vision and Applications (1993) 6:69-82. The OZZ method first finds horizontal and vertical lines using OZZ movements and then identifies slanted or angled lines. This is the fastest bitmap based method that has been encountered. Although faster than traditional straight line detection algorithms, the OZZ method still requires considerable time and memory to process large engineering drawings. In addition, the OZZ method requires a user to specify numerous adjustment parameters for effective processing of a given image type. The performance of the OZZ algorithm is sensitive to the setting of these parameters.
In addition, structured drawings are often scanned and stored in run length encoded format. Since most skew correction methods, such as the prior art methods described above, are designed to work with unencoded or bitmapped drawings, encoded drawings must be converted to unencoded form before being processed, thus requiring more memory and processing time.